package main

import (
	"container/list"
	"fmt"
)

type Node2 struct {
	Data  int
	Left  *Node2
	Right *Node2
}

type Stack struct {
	list *list.List
}

func (s *Stack) Push(data interface{}) {
	s.list.PushBack(data)
}

func (s *Stack) Pop() interface{} {
	if e := s.list.Back(); e != nil {
		s.list.Remove(e)
		return e.Value
	}
	return fmt.Errorf("111")
}

func (s *Stack) Empty() bool {
	return s.list.Len() == 0
}

func main() {
	tree := &Node2{Data: 0}
	tree1 := &Node2{Data: 1}
	tree22 := &Node2{Data: 2}
	tree3 := &Node2{Data: 3}
	tree4 := &Node2{Data: 4}
	tree5 := &Node2{Data: 5}
	tree1.Left = tree3
	tree1.Right = tree4
	tree22.Right = tree5
	tree.Left = tree1
	tree.Right = tree22
	//Pre(tree)
	In(tree)
}

func Pre(tree *Node2) {
	stack := &Stack{
		list: new(list.List),
	}
	stack.Push(tree)
	for !stack.Empty() {
		cur := stack.Pop().(*Node2)
		fmt.Println(cur.Data)
		if cur.Right != nil {
			stack.Push(cur.Right)
		}
		if cur.Left != nil {
			stack.Push(cur.Left)
		}
	}
}

func In(tree *Node2) {
	stack := &Stack{
		list: new(list.List),
	}
	cur := tree
	for {
		for cur != nil {
			stack.Push(cur)
			cur = cur.Left
		}
		if stack.Empty() {
			break
		}
		cur = stack.Pop().(*Node2)
		fmt.Println(cur.Data)
		cur = cur.Right
	}
}
